﻿/*
题目：跳跃游戏 VI

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。

请你返回你能得到的 最大得分 。

https://leetcode.cn/problems/jump-game-vi/description/?envType=daily-question&envId=2024-02-05
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // **KEY** 动态规划，使用单调栈维护 这个窗口 , 减少遍历过程
    int maxResult(vector<int>& nums, int k) {
        // 每次可以跳 [i + 1, i + k] 的点
        // 需要使用单调栈优化，因为窗口为 k，单调递减栈
        int n = nums.size();
        vector<int> dp(n, INT_MIN);
        deque<int>  deq;

        dp[0] = nums[0];
        deq.push_back(0);

        // 到 i 下标的最大和
        for (int i = 1; i < n; i++) {
            // 弹出窗口外的元素
            while (!deq.empty() && i - deq.front() > k) {
                deq.pop_front();
            }

            // 那么栈顶元素就是窗口内的最大值
            dp[i] = dp[deq.front()] + nums[i];
            // 开始维护单调栈
            while (!deq.empty() && dp[deq.back()] <= dp[i]) {
                deq.pop_back();
            }

            deq.push_back(i);
        }

        return dp[n - 1];
    }
};